package sortAlgorithm;

import com.sun.scenario.effect.impl.state.LinearConvolveKernel;

// 归并排序
public class MergeSort {

    static int[] temp = new int[7];// 临时数组
    static int[] nums = new int[]{2,1,5,4,6,8,0};// 需要排序的数组

    // 将数组分成多个小组
    public static void mergeSort(int[] arr,int left,int right){
        if(left < right){
            int middle = (left + right) / 2;
            mergeSort(arr,left,middle);// 将左边继续分解
            mergeSort(arr,middle+1,right);// 将右边继续分解
            // 合并 将数组 和 左右 中间位置传递过去
            merge(arr, left, middle + 1, right);
        }
    }

    // 合并
    public static void merge(int[] arr, int left, int middle, int right){
        int i = left, j = middle;
        int p = left;
        // 对两个小组的头元素进行比较排序
        while (i < middle && j <= right){
            if (arr[i] < arr[j]){ // 如果左边的这组比右边的这组小，那么把它赋值到临时数组
                temp[p++] = arr[i++];
            }else {
                temp[p++] = arr[j++];
            }
        }

        // 如果其中一个数组已经比较完了，那把另外一个数组依次添加到临时数组中
        while(i < middle){
            temp[p++] = arr[i++];
        }

        while(j <= right){
            temp[p++] = arr[j++];
        }

        // 将归并后(排序后的)的数组赋值给原数组
        for (int k = 0; k < p; k++) {
            nums[k] = temp[k];
        }

    }

    // main
    public static void main(String[] args) {
        // 建立一个无序链表
        LinkedNode l1 = new LinkedNode(6,null);
        LinkedNode l2 = new LinkedNode(1,l1);
        LinkedNode l3 = new LinkedNode(7,l2);
        LinkedNode l4 = new LinkedNode(4,l3);
        LinkedNode l5 = new LinkedNode(8,l4);
        LinkedNode l6 = new LinkedNode(3,l5);

        // 实例化一个链表排序类
        LinkSortByMerge ls = new LinkSortByMerge();
        LinkedNode rs = ls.divide(l6);
        while(rs.next != null){
            System.out.println(rs.value);
            rs = rs.next;
        }
    }
}

// 归并排序的链表实现
class LinkedNode{ // 声明链表节点
    int value;
    LinkedNode next;
    public LinkedNode(int value, LinkedNode next){
        this.value = value;
        this.next = next;
    }
}

class LinkSortByMerge{
    // 分治
    public LinkedNode divide(LinkedNode head){
        if(head.next == null){
            return head;
        }

        LinkedNode fast = head;
        LinkedNode slow = head;
        // 当fast走完了整个链表，slow在链表的中间
        while (fast.next != null) {
            fast = fast.next;
            if (fast.next != null) {
                fast = fast.next;
                slow = slow.next;
            }
        }
        // 这个时候slow是停留在链表的中间  fast是在链表的最后一个结点
        LinkedNode right = divide(slow.next);//先把后半段继续分组
        // 将前半段斩断
        slow.next = null;
        LinkedNode left = divide(head);// 再前半段分组
        return merge(left, right); // 进行合并
    }

    // 合并
    public LinkedNode merge(LinkedNode left, LinkedNode right){

        LinkedNode temp = null;
        // 弄一个哑结点指向temp
        LinkedNode dummy = temp;
        while(left != null && right != null){
            if(left.value < right.value){
                temp = new LinkedNode(right.value, null);
                right = right.next;
            }else{
                temp = new LinkedNode(left.value, null);
                left = left.next;
            }
            temp = temp.next;
        }

        while(left != null){
            temp = new LinkedNode(left.value, null);
            left = left.next;
            temp = temp.next;
        }

        while(right != null){
            temp = new LinkedNode(right.value, null);;
            right = right.next;
            temp = temp.next;
        }
        return dummy;
    }
}